SherbyNet - /page/wikibook/entry.mu

Micron Document

Pseudo-Boolean function

12.4 KB · ⇊ 8 parts · ⤓ Micron 12.4 KB · ⤓ HTML 54.8 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In mathematics and optimization, a pseudo-Boolean function is a function of the form

f : B n → → R , {\displaystyle f:\mathbf {B} ^{n}\to \mathbb {R} ,}

where B = {0, 1} is a Boolean domain and n is a nonnegative integer called the arity of the function. A Boolean function is then a special case, where the values are also restricted to 0 or 1.

Contents

• Representations

• Optimization

• Submodularity

• Roof Duality

• Quadratizations

• Polynomial Compression Algorithms

• See also

• Notes

• References

Representations

Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial:cite-ref-1[1]cite-ref-2[2]

f ( x ) = a + ∑ ∑ i a i x i + ∑ ∑ i < j a i j x i x j + ∑ ∑ i < j < k a i j k x i x j x k + … … {\displaystyle f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots }

The degree of the pseudo-Boolean function is simply the degree of the polynomial in this representation.

In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function f {\displaystyle f} that maps { − − 1 , 1 } n {\displaystyle \{-1,1\}^{n}} to R {\displaystyle \mathbb {R} } . Again in this case we can uniquely write f {\displaystyle f} as a multi-linear polynomial: f ( x ) = ∑ ∑ I ⊆ ⊆ [ n ] f ^ ^ ( I ) ∏ ∏ i ∈ ∈ I x i , {\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},} where f ^ ^ ( I ) {\displaystyle {\hat {f}}(I)} are Fourier coefficients of f {\displaystyle f} and [ n ] = { 1 , . . . , n } {\displaystyle [n]=\{1,...,n\}} .

Optimization

Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is NP-hard. This can easily be seen by formulating, for example, the maximum cut problem as maximizing a pseudo-Boolean function.cite-ref-boros2002-3-0[3]

Submodularity

The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition

f ( x ) + f ( y ) ≥ ≥ f ( x ∧ ∧ y ) + f ( x ∨ ∨ y ) , ∀ ∀ x , y ∈ ∈ B n . {\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}}),\;\forall {\boldsymbol {x}},{\boldsymbol {y}}\in \mathbf {B} ^{n}\,.}

This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).

Roof Duality

If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value.cite-ref-boros2002-3-1[3] Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.cite-ref-boros2002-3-2[3]

Quadratizations

If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables. One possible reduction is

− − x 1 x 2 x 3 = min z ∈ ∈ B z ( 2 − − x 1 − − x 2 − − x 3 ) {\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})}

There are other possibilities, for example,

− − x 1 x 2 x 3 = min z ∈ ∈ B z ( − − x 1 + x 2 + x 3 ) − − x 1 x 2 − − x 1 x 3 + x 1 . {\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}

Different reductions lead to different results. Take for example the following cubic polynomial:cite-ref-kahl2011-4-0[4]

f ( x ) = − − 2 x 1 + x 2 − − x 3 + 4 x 1 x 2 + 4 x 1 x 3 − − 2 x 2 x 3 − − 2 x 1 x 2 x 3 . {\displaystyle \displaystyle f({\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{3}.}

Using the first reduction followed by roof duality, we obtain a lower bound of −3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of −2 and the optimal assignment of every variable (which is ( 0 , 1 , 1 ) {\displaystyle {(0,1,1)}} ).

Polynomial Compression Algorithms

Consider a pseudo-Boolean function f {\displaystyle f} as a mapping from { − − 1 , 1 } n {\displaystyle \{-1,1\}^{n}} to R {\displaystyle \mathbb {R} } . Then f ( x ) = ∑ ∑ I ⊆ ⊆ [ n ] f ^ ^ ( I ) ∏ ∏ i ∈ ∈ I x i . {\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.} Assume that each coefficient f ^ ^ ( I ) {\displaystyle {\hat {f}}(I)} is integral. Then for an integer k {\displaystyle k} the problem P of deciding whether f ( x ) {\displaystyle f(x)} is more or equal to k {\displaystyle k} is NP-complete. It is proved in cite-ref-crowston2011-5-0[5] that in polynomial time we can either solve P or reduce the number of variables to O ( k 2 log ⁡ ⁡ k ) . {\displaystyle O(k^{2}\log k).} Let r {\displaystyle r} be the degree of the above multi-linear polynomial for f {\displaystyle f} . Then cite-ref-crowston2011-5-1[5] proved that in polynomial time we can either solve P or reduce the number of variables to r ( k − − 1 ) {\displaystyle r(k-1)} .